// Created by WXX on 2021/12/24 20:01
#include "MyTree.h"

/**
 * 执行用时：40 ms, 在所有 C++ 提交中击败了73.41%的用户
 * 内存消耗：32.3 MB, 在所有 C++ 提交中击败了39.88%的用户
 */
class Solution {
public:
    TreeNode* sufficientSubset(TreeNode* root, int limit) {
        dfs(root, 0, limit);
        return root;
    }

    void dfs(TreeNode* &root, int sum, int limit) {
        sum += root->val;
        if (!root->left && !root->right) {
            if (sum < limit) root = NULL;
        } else {
            if (root->left) dfs(root->left, sum, limit);
            if (root->right) dfs(root->right, sum, limit);
            if (!root->left && !root->right) root = NULL;
        }
    }
};

int main() {

    int nu = INT_MAX;
    vector<int> nums = {
            1,
            2, 3,
            4, -99, -99, 7,
            8, 9, -99, -99, 12, 13, -99, 14,
    };
    TreeNode *root = MyTree(nums).getRoot();
    OutputBasicArray2D(MyTree().levelOrder(Solution().sufficientSubset(root, 1)));

    return 0;
}
